//package work.rightAnswer;
//
//class UnionFind{
//    int[] parents;//下标表示元素，映射关系为 横坐标*列数+纵坐标:元素(横坐标，纵坐标);值表示父节点
//
//    public UnionFind(int totalNums){
//        parents = new int[totalNums];
//        //将所以节点的父节点设为自己
//        for (int i = 0; i < totalNums; i++) {
//            parents[i] = i;
//        }
//    }
//
//
//    public void union(int a,int b){
//        //a b 分为表示元素映射过来的下标
//        int aF = findParent(a);
//        int bF = findParent(b);
//        if(aF != bF){
//            parents[aF] = bF;
//        }
//    }
//
//    public int findParent(int a) {
//        //遍历到a的父节点
//        while (parents[a]!=a){
//            parents[a] = parents[parents[a]];
//            a = parents[a];
//        }
//
//        return a;
//    }
//
//    public boolean isUnioned(int a,int b){
//        int aF = findParent(a);
//        int bF = findParent(b);
//
//        return aF == bF;
//    }
//}
//
//
//
//class Solution {
//    public void solve(char[][] board) {
//        int rows = board.length;
//        int cols = board[0].length;
//        //多出的最后一个元素作为公共父节点
//        UnionFind unionFind = new UnionFind(rows*cols+1);
//        int parents = rows*cols;
//
//        //遍历board
//        for (int i = 0; i < rows; i++) {
//            for (int j = 0; j < cols; j++) {
//                //将边界的'O'全部连在一起
//                if(board[i][j]=='O') {
//                    //边界
//                    if (i == 0 || j == 0 || i == rows - 1 || j == cols - 1) {
//                        unionFind.union(node(i, cols, j), parents);
//                    } else {
//                        //其他的’O‘节点，把上下左右为’O'的节点都连起来
//                        if (i>0&&board[i-1][j]=='O'){
//                            unionFind.union(node(i,cols,j),node(i-1,cols,j));
//                        }
//                        if (i<rows-1&&board[i+1][j]=='O'){
//                            unionFind.union(node(i,cols,j),node(i+1,cols,j));
//                        }
//                        if (j>0&&board[i][j-1]=='O'){
//                            unionFind.union(node(i,cols,j),node(i,cols,j-1));
//                        }
//                        if (j<cols-1&&board[i][j+1]=='O'){
//                            unionFind.union(node(i,cols,j),node(i,cols,j+1));
//                        }
//                    }
//                }
//            }
//        }
//
//        //再次遍历，将与parents一个连通区域的改为’O‘，剩下改为'X'
//        for (int i = 0; i < rows; i++) {
//            for (int j = 0; j < cols; j++) {
//                if(unionFind.isUnioned(node(i,cols,j),parents)){
//                    board[i][j] = 'O';
//                }else {
//                    board[i][j] = 'X';
//                }
//            }
//        }
//
//
//    }
//
//
//    public int node(int i,int cols,int j){
//            return i*cols + j;
//    }
//}